import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 刘柄华
 * Date: 2022-06-03
 * Time: 19:18
 */

//查找两个字符串a,b中的最长公共子串

    /*
    * 动态规划求解
    *
    * 子问题为: str1的前i个字符
    * */
public class TestDemo01 {
    public static String getMaxSubLen(String str1, String str2){
        char[] arr1 = str1.toCharArray();
        char[] arr2 = str2.toCharArray();
        int len1 = str1.length();
        int len2 = str2.length();

        //最长字串的起始位置
        int start = 0;
        //最长字串的长度
        int maxLen = 0;

        //状态: 以a的第i个字符结尾和以b的第j个字符结尾的最长公共字串的长度
        int[][] maxSubLen = new int[len1+1][len2+1];

        for(int i=1;i<=len1;i++){
            for (int j = 1; j <=len2 ; j++) {
                if(arr1[i-1] == arr2[j-1]){
                    maxSubLen[i][j] = maxSubLen[i - 1][j - 1] + 1;
                    if(maxLen < maxSubLen[i][j]){
                        maxLen = maxSubLen[i][j];
                        start = i - maxLen;
                    }
                }
            }
        }
        return new String(arr1,start-1,maxLen-1);
    }

    public static void main1(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextLine()){
            String str1 = sc.nextLine();
            String str2 = sc.nextLine();

            if(str1.length()<str2.length()){
                System.out.println(getMaxSubLen(str1,str2));
            }else {
                System.out.println(getMaxSubLen(str2,str1));
            }
        }
    }

    public static void main(String[] args) {
        String s1 = "lalalala";
        char[] arr1 = s1.toCharArray();
        String s2 = new String(arr1, 1, 5);
        System.out.println(s2);
        System.out.println(s1.substring(2,7));
    }
}
